<!DOCTYPE group PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<group>

%tableofcontents;

<p>This tutorial shows how to use the <a href="%dox:kmeans;">K-means
algorithm</a> using the VlFeat implementation of Llloyd's algorithm as
well as other faster variants.</p>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kmeans.introduction">Running K-means</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>KMeans is a clustering algorithm. Its purpose is to partition a set
of vectors into $K$ groups that cluster around common mean
vector. This can also be thought as <em>approximating</em> the input
each of the input vector with one of the means, so the clustering
process finds, in principle, the best dictionary or codebook to
<em>vector quantize</em> the data.</p>

<p>Consider a dataset containing 1000 randomly sampled 2D points:</p>

<precode type='matlab'>
numData = 5000 ;
dimension = 2 ;
data = rand(dimension,numData) ;
</precode>

<p>The function <code>vl_kmeans</code> can be used to cluster the data
into, say, 30 groups:</p>

<precode type='matlab'>
numClusters = 30 ;
[centers, assignments] = vl_kmeans(data, numClusters);
</precode>

<p>By default, this uses the
the <a href="%dox:kmeans-lloyd;">Lloyd</a> algorithm, a method that
alternates between optimizing the cluster centers and the
data-to-center assignments. Once this process terminates, the
matrix <code>centers</code> contains the cluster centers and the
vector <code>assignments</code> the (hard) assignments of the input
data to the clusters. The cluster centers are also
called <em>means</em> because it can be shown that, when the
clustering is optimal, the centers are the means of the corresponding
data points. The cluster centers and assignments can be visualized as
follows:</p>

<div class="figure">
  <image src="%pathto:root;demo/kmeans_2d_rand.jpg"/>
  <div class="caption">KMeans clustering of 5000 randomly sampled data
  points. The black dots are the cluster centers.</div>
</div>

<p>Given a new data point <code>x</code>, this can be mapped to one of
the clusters by looking for the closest center:</p>

<precode type='matlab'>
x = rand(dimension, 1) ;
[~, k] = min(vl_alldist(x, centers)) ;
</precode>

<p>For larger datastes, this process may be significantly accelerated
by using <a href="%pathto:tut.kdtree;">KDTrees</a> or other
approximate nearest neighbor procedures.</p>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kmeans.initialization">Choosing an initialization method</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>K-means uses local optimization algorithms and is therefore
sensitive to initalization. By default, <code>vl_kmeans</code>
initializes the cluster centers by picks $K$ data points at
random. Other initalization strategies can be selected as well.
<a href='%dox:kmeans-plus-plus'>kmeans++</a> is a popular method that
greedily pick $K$ data points that are maximally different, and can be
use as follows:</p>

<precode type='matlab'>
[centers, assignments] = vl_kmeans(data, numClusters, 'Initialization', 'plusplus') ;
</precode>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kmeans.algorithm">Choosing an optimization algorithm</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>In addition to the original KMeans algorithm proposed by Lloyd,
<code>vl_kmeans</code> supports two additional
algorithms: <a href="%dox:kmeans-elkan">Elkan's</a> variant, an exact
algorithm using an acceleration technique based the triangular
inequality, and
<a href="%dox:kmeans-ann;">ANN</a>, an approximated algorithm using
approximate nearest neighbours.</p>

<p>These optimization methods can be enabled by setting the
<code>'Algorithm'</code> parameter to <code>'Lloyd'</code>,
<code>'Elkan'</code> or <code>'ANN'</code> respectively. When using
the <code>'ANN'</code> algorithm, the user can also specify the
parameters <code>'MaxNumComparisons'</code>
and <code>'NumTrees'</code> to <a href="%dox:kdtree;">configure
the KD-tree</a> used used as ANN. In
particular, <code>'MaxNumComparisons'</code> controls the trade-off
between approximation quality and speed.</p>

<p><code>vl_demo_kmeans_ann_speed</code> compares the speed of the
three algorithms. Because of the random initialization, each of the
KMeans calls converges to a different local minimum in a different
amount of iterations. In order to measure more accurately the speed of
each pass, a relatively small number
of <code>'MaxNumIterations'</code> option) is selected. Note that the
speedup factor are in general much more dramatic when truly large
datasets are considered.</p>

<div class="figure">
<image src="%pathto:root;demo/kmeans_speed.jpg"/>
<div class="caption">Comparisons of Elkan, Lloyd and ANN for different
values of <code>MaxNumComparison</code>, expressed as a fraction of
the number of clusters. The figure reports the duration, final energy
value, and speedup factor, using both the serial and parallel versions
of the code. The figure was generated using
<code>vl_demo_kmeans_ann_speed</code>.</div>
</div>

</group>

